---
title: "L2-016 愿天下有情人都是失散多年的兄妹"
created: 2025-11-28
tags:
  - 算法
---

# L2-016 愿天下有情人都是失散多年的兄妹

## 题目 [L2-016 愿天下有情人都是失散多年的兄妹](https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=994805061769609216&page=1)

![[image-661990f2.png]]

## 思路分析

![[image-bc2a2773.png]]

使用邻接表把所有的关系存起来 查询时使用dfs把双方五代全部进行标记 如果有重复的 就说明找到了公共祖先 不能通婚

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;

const int N=1e5+10;
vector<int> v[N];
char gender[N];
bool isFound=false;
bool st[N];

void dfs(int u,int depth){
	if(depth>=5)	return;
	if(st[u]){
		isFound=true;
		return;
	}
	st[u]=true;
	for(auto parent : v[u]){
		dfs(parent,depth+1);
	}
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n;cin>>n;
	while(n--){
		int curId,fatherId,motherId;
		char curGender;
		cin>>curId>>curGender>>fatherId>>motherId;
		gender[curId]=curGender;
		if(fatherId!=-1){
			gender[fatherId]='M';
			v[curId].push_back(fatherId);
		}
		if(motherId!=-1){
			gender[motherId]='F';
			v[curId].push_back(motherId);
		}
	}

	int k;cin>>k;
	while(k--){
		int x,y;cin>>x>>y;
		isFound=false;
		memset(st,false,sizeof st);
		dfs(x,0);
		dfs(y,0);
		if(gender[x]==gender[y])	cout<<"Never Mind"<<endl;
		else{
			if(!isFound)	cout<<"Yes"<<endl;
			else	cout<<"No"<<endl;
		}
	}

	return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[L2-015 互评成绩|L2-015 互评成绩]] 🏠 [[00-天梯赛]] ➡️ [[L2-017 人以群分|L2-017 人以群分]]